Пирамида изображений

Пирамида изображений

Пирами́да изображе́ний — класс кратномасштабных иерархических структур данных, разработанных для применения в прикладных задачах машинного зрения, сжатия информации, анализа текстур растровых изображений и т. п. Такие структуры содержат на каждом своём уровне иерархии уменьшенную версию предыдущего изображения, каждая из которых рекурсивно вычисляется на базе предыдущих слоёв посредством применения однотипной операции (например — сглаживания). При этом всякому уровню иерархии ставится в соответствие актуальный для решаемой задачи параметр масштаба, который описывает интересующие свойства изображения.

Краткая история

Возникновение интереса специалистов по математической обработке изображений к иерархическим пирамидам связано с необходимостью решать некоторые прикладные задачи в условиях априори неизвестного масштаба искомых свойств или признаков. Так как этот характерный размер не определён, то возможным путём к решению является декомпозиция исходного изображения на иерархическую систему в которой каждый слой представлен своим собственным масштабом, артикулирующим отдельный диапазон признаков. Аналогичным образом устроена система обработки видеоинформации у биологических объектов.

Появление первых иерархических пирамид датируется концом 1970-х годов, выбор их названия был продиктован чисто внешней зрительной ассоциацией. В 1980-х началось активное использование иерархических пирамид в задачах смешивания изображений и поиска на них соответствия между разномасштабными элементами и структурами. В это же самое время завершилось создание непрерывных версий пирамидальных структур для пространственно-масштабной обработки. Однако в конце 1980-х годов традиционным пирамидам пришлось потесниться из-за активного внедрения вейвлет-преобразований.

Описание

По своей сути пирамида изображений может рассматриваться как набор представлений, упорядоченный в форме вертикальной иерархии по мере уменьшения некоего масштаба. Обычно в основании пирамиды располагается оригинальное изображение высокого разрешения, а по мере движения вверх масштаб и разрешение уменьшаются. В результате, на вершине оказывается самое грубое приближение с низким качеством и информативностью.

Как правило, в целях генерирования пирамиды для удобства её представления изначальное изображение пересчитывается в размерности, кратные степени числа 2. Если исходные данные имели вид массива пикселов $N\times N$, то эта запись эквивалентна $2^{n}\times 2^{n}$, где $n=\log _{2}N$. В таком виде параметр $n$ играет роль высоты пирамиды, выраженной в количестве представлений исходного изображения (слоёв).

Первый слой (приближение) пирамиды можно получить последовательным усреднением соседних пикселей, результатом которого станет массив ${\frac {N}{2}}\times {\frac {N}{2}}$. Применяя эту процедуру рекурсивно получается набор изображений с экспоненциально уменьшающимися размерами. При этом, пикселы промежуточных изображений содержат в себе информацию о квадратных блоках пикселов нижележащих слоёв с более высоким разрешением. Тогда произвольно выбранный промежуточный слой будет содержать в себе $2^{j}\times 2^{j}$ пикселов, где 0 ≤ j < n, а полное количество пикселов в пирамиде, содержащей $k$ слоёв:

$N^{2}\left(1+{\frac {1}{4^{1}}}+{\frac {1}{4^{2}}}+{\frac {1}{4^{3}}}+...+{\frac {1}{4^{k}}}\right)\leq {\frac {4}{3}}N^{2}.$

Промежуточные узлы пирамиды не обязательно должны представлять собой взвешенное среднее по интенсивности из нижних слоёв. Вместо интенсивности в них могут храниться другие виды информации, например — дескрипторы текстур или параметры геометрических элементов (линий, кривых и т. п.)

Применение пирамид

Наиболее очевидным полезным свойством кратномасштабных пирамид является возможность снижения вычислительных затрат различных алгоритмов за счёт применения принципа «разделяй и властвуй» ^{[уточнить]}. Также к преимуществам представления двумерного изображения в виде пирамиды считается соотнесение его локальных элементов и свойств с глобальными. Это позволяет конструировать древовидные структуры данных для многофакторного анализа, включающего в себя локальную и глобальную информацию. Например, связывая значения отдельных пикселов со свойствами окружающих их регионов.

Разновидности

Классическими видами пирамидальных иерархий считаются гауссовы пирамиды и пирамиды лапласианов. Благодаря своим хорошо изученным свойствам они получили широкое распространение в целом ряде практических приложений.

Гауссова пирамида состоит из слоёв, каждый из которой получается из предыдущего с помощью сглаживания симметричной гауссоидой (низкочастотная фильтрация) и последующей за этим дискретизацией (см. Фильтр Гаусса). Совокупность этих слоёв называется грубой шкалой изображения. Областью применения гауссовых пирамид обычно являются задачи поиска изображений по масштабу и пространственного сопоставления различных изображений.

Пирамиды лапласианов вычисляются последовательным сглаживанием и децимацией начальных данных. При этом, каждый уровень пирамиды является уточнением предыдущих и соответствует отдельной полосе частот (полосовая фильтрация). В отличие от гауссовых пирамид, этот тип данных допускает более высокую степень сжатия информации. В дополнение к этому исходное изображение может быть легко восстановлено на основе суперпозиции промежуточных слоёв, что позволяет не хранить его в памяти.

Источники

• Гонсалес, Р. Цифровая обработка изображений / Р. Гонсалес, Р. Вудс. — М. : «Техносфера», 2005. — 1072 с. — ISBN 5-94836-028-8.
• Форсайт, Д. Компьютерное зрение. Современный подход / Д. Форсайт, Ж. Понс. — М. : «Вильямс», 2004. — 928 с. — ББК 32.973.26-018.2.75. — УДК 681.3.07. — ISBN 5-8459-0542-7.
• Jähne, B. Digital Image processing : [англ.]. — 5th ed. — Springer-Verlag, 2002. — ISBN 3-540-67754-2.
• Jayaraman, S. Digital Image Processing. — Tata McGraw Hill, 2009. — ISBN 978-0-07-014479-8.
• Montanvert, A. Hierarchical Image Analysis Using Irregular Tesselations : [англ.] / G. Goos, J. Hartmanis. — Computer Vision - ECCV 90. — Springer-Verlag, 1990. — ISBN 3-540-52522-X.
• Szeliski, R. Computer Vision Algorithms and Applications : [англ.]. — Springer, 2011. — ISBN 978-1-84882-934-3. — doi:10.1007/978-1-84882-935-0.
• Dictionary of Computer Vision and Image Processing : [англ.]. — 2th ed. — John Wiley & Sons Ltd, 2014. — ISBN 978-1-119-94186-6.
• Multiresolution Image Processing and Analysis : [англ.] / A. Rosenfeld. — Springer-Verlag, 1984. — ISBN 978-3-642-51592-7. — doi:10.1007/978-3-642-51590-3.